Hugi Magazine #33: MP3 Power

Introduction

You are reading this because you're somewhat involved in the demoscene. So, you've probably seen a fractal or 20000. You've no doubt seen mandelbrots, julias, maybe even some others. Well, one kind of fractal image is one not seen that often, and is described as Diffusion-Limited Aggregation. Nice big words, eh? Well, DLA isn't really that complicated.

What does it look like, you ask? Here're a couple screenshots of various examples of well-executed DLA:

Common 2D DLA (by Paul Bourke)

3D DLA featured in YUP's demo "Purple", and also in this article's example, included in the bonus pack with this issue.

Generation

Looks pretty neat, huh? Unlike some other fractal images, which are generated by given x, y, and possibly z coordinates, DLA is generated by taking a blank white image with a black pixel in the center, and introducing new pixels into the image that move randomly until they meet another black pixel or the boundaries of the simulation, at which point they become part of the image for other pixels to merge with. Kind of hard to explain with words, but thankfully for you programmers, we have pseudo-code:

Create a blank image
Plot a dot in the center
Repeat for a given number of particles:
	Place particle randomly in the simulation
	Repeat forever:
		If particle is inside boundaries:
			If any pixel around particle isn't blank:
				Plot particle
				Break forever loop
			End If
		Else
			Limit particle's coordinates so it's inside the boundary
			Plot particle
			Break forever loop
		End If
		Move particle randomly
	End Loop
End Loop

Now it may be a bit easier to understand. If not, here's another description I found on Paul Bourke's site:

"Another more colourful description involves a city square surrounded by taverns. Drunks leave the taverns and stagger randomly around the square until they finally trip over one of their insensate companions at which time, lulled by the sounds of peaceful snoring, they lie down and fall asleep. The tendril like structure is an aerial view of the sleeping crowd in the morning."

I liked that one a little better, too. :) You should now understand that DLA is called DLA because particles (or drunks) move around randomly (diffusion) until they hit previous particles or the boundaries, where they attach themselves (aggregate) to the overall structure being generated. It's "diffusion-limited" because the final structure is limited by the particle's movement.

Let us look at that pseudo-code once more. We start the simulation with a blank image or grid. This can be most easily defined as a 2D or 3D grid of booleans, where at the beginning of the simulation each position is set to "false". Next, we plot a dot in the center, or rather, set the position in the middle of our grid to "true". Then, we loop through each of our particles. A particle, really, is just defined as coordinates in our grid. So for each particle, we set its initial coordinates randomly inside our grid. Then we execute a loop that repeats until the particle "escapes" our simulation (exceeds its boundaries) or touches a "true" value in our grid. In this loop, the current particle is first checked to make sure it's inside our grid. If it is, then the 26 points around our particle's position are all checked to see if they're true. If any of them are, then we set the particle's position to true and move on to the next particle. If, when we checked if the particle was inside the simulation and it wasn't, modify its coordinates to be sure it's inside, then set its position to true and move on. Finally, if the particle wasn't outside the simulation or touching any "true" positions, we move it by choosing a random number between 0 and 5. If it's zero, move it to the left, if it's one, move it to the right, etc. Whew, a lot to take in! Not really, just lots of typing. :)

DLA in Realtime

If you haven't figured it out by now, this method is awefully slow at the grid resolutions it's usually performed in. Aren't we supposed to use this in demos? How is that possible if it's this slow?

Well, some of you may hate to hear this, but it's all summed up in one word - precalculation. I know, some of you hardcore-optimising coders probably hate me right now (Sorry, Shockwave!), but for a fractal like this in this day and age, it IS necessary. Also, with this method I'm about to describe, delta timing is made easier, so it should even out. ;)

Doing fractals like this is actually pretty easy to do in realtime. I've used the same method for attractors, and I believe Preacher of Traction uses a similar method. How it works is simple: Create some arrays to store colors, coordinates, alpha values, etc, for each particle you want in your simulation (my simulation used 20000 particles). Then, do each particle's calculation in a temporary grid, and when you set its position to true in the grid, store the particle's data in the forementioned arrays. Now, all you have to do in realtime is gradually increase the number of particles that actually get drawn (i.e. frame 1 draws 2 particles, frame 2 draws 4), so it looks like the simulation is being done in realtime, when actually, you're just limiting the particles you draw!

Conclusion

By now, you should have at least a basic understanding of what DLA is and how to implement it in realtime. There are some more points I could go into, such as how to draw this in a demo, but I think that's up to you to decide how you want it. I used OpenGL points, but you can use whatever you wish. Just be creative - when you get the simulation working, play with different colors based on position, particle number, etc. You can create some really pretty images with a little time and creativity. ;)

Greetings

As my final words, these are some (certainly not all) of the people I would like to greet:

• Waffle
• Carpets
• White Noise
• Shockwave
• Clyde Radcliffe
• Blitz Amateur
• Tetra
• Roly
• Rbraz
• Morgan
• Preacher
• Grip
• Vulture
• Rale
• Zeebr
• Lord Kelvin

Now go read the rest of Hugi 33 !!